The present invention relates generally to asynchronous transfer mode (ATM) communication systems and more particularly to ATM cell processing operations in an ATM communication system.
Asynchronous transfer mode (ATM) communication systems are designed to support high-speed, low-delay multiplexing and switching of voice, data, video and other types of user information traffic. An ATM system segments user traffic into fixed-length 53-byte cells. A 5-byte header in each cell typically includes a virtual channel identifier (VCI) and a virtual path identifier (VPI) associated with the corresponding cell. The VCI and VPI fields together identify a virtual connection (VC) which is established when a user requests a network connection in an ATM system. Additional details regarding these and other aspects of ATM systems can be found in the ATM Forum, xe2x80x9cATM User-Network Interface Specification,xe2x80x9d Version 3.1, September, 1994, and in Martin de Prycker, xe2x80x9cAsynchronous Transfer Mode: Solution for Broadband ISDN,xe2x80x9d Ellis Horwood, New York, 1993, both of which are incorporated by reference herein. The allocation of available transmission opportunities or slots to user traffic cells is generally referred to as cell scheduling.
One possible ATM cell scheduling technique could involve calculating for a given VC an ideal time at which the VC should be serviced by allocating a cell to that VC. An ATM scheduling system could then mark in a stored table, list or other type of schedule the fact that a given VC X is ready for scheduling at a time Y. Because one or more other active VCs may have previously requested servicing at time Y, such a cell scheduling system would typically require a two-dimensional list of scheduling requests in which one dimension is time and the other dimension is the list of VCs scheduled to be serviced at a given time.
A significant problem with such a two-dimensional cell schedule is that it makes it difficult for a scheduling system to determine when a particular VC should be scheduled for servicing due to the fact that the calculation can no longer be based on time alone. This is because there could be a back-up of arbitrary depth at any given scheduled time. As a result, a servicing processor may arrive late at successive scheduled times. VCs that are scheduled further out in time could have been scheduled earlier in time had the scheduling system been aware of the delays that would be encountered by the servicing processor. For example, the scheduling system could have scheduled a given VC earlier in time while maintaining the necessary elapsed time between successive cell transmission events if it were able to account for the delays. This two-dimensional scheduling technique results in inefficient scheduling and thus reduced system throughput.
Prior art ATM cell processors also suffer from a number of other drawbacks. For example, most available cell processors typically utilize either a hard-wired approach to provide increased throughput speed or a programmable approach which provides a high degree of flexibility but at the cost of reducing throughput speed. Another problem is that prior art cell processor approaches generally do not allow system designers to provide a common, reprogrammable architecture suitable for use in a wide variety of different ATM-based products. Other serious problems with prior art cell processing include the latency associated with accessing control information from static random access memory (SRAM) or other types of control or system memory, the scheduling of constant bit rate (CBR) traffic in the presence of variable bit rate (VBR) traffic, and the failure of the prior art devices to provide support for virtual path (VP) tunneling.
As is apparent from the above, there is a need for improved ATM cell scheduling, servicing and other processing techniques which avoid the above-noted problems of the prior art.
The present invention provides apparatus and methods for processing asynchronous transfer mode (ATM) cells in an ATM communication system. The invention provides improved cell scheduling and servicing techniques as well as an improved ATM cell processor architecture. An ATM cell processor in accordance with the invention is particularly well-suited for use in high-speed ATM cell processing applications, and can provide cell throughput at speeds typically associated only with fully hard-wired devices, while simultaneously providing the increased flexibility of a programmable device. An ATM communication system based on a cell processor in accordance with the present invention can be readily configured to provide different operating parameters and is therefore relatively insensitive to changes in ATM standards. Many such changes can be implemented in a cell processor of the present invention through relatively simple software and/or firmware modifications.
One aspect of the invention involves a method of allocating cells in an ATM communication system. The method includes the step of generating a first group of bits in the form of a primary scoreboard. Each bit of the primary scoreboard represents a cell time slot on a transmission link in the communication system, and the value of a given primary scoreboard bit indicates whether or not the corresponding cell time slot is available for transmission. In response to a cell scheduling request of a given virtual connection in the ATM system, a processor directs the searching of the primary scoreboard beginning at a bit corresponding to a target time slot and proceeding through the scoreboard until a bit corresponding to an available time slot is identified. The available time slot is then scheduled by setting the identified primary scoreboard bit, and storing a connection identifier (ID) for the virtual connection in a connection ID table at a location corresponding to the identified primary scoreboard bit. The primary scoreboard and connection ID table can both be maintained in an external control memory which the ATM cell processor accesses through a high-speed memory port. Alternatively, the primary scoreboard and/or connection ID table can be maintained in a set of memory locations internal to the ATM cell processor to further reduce scheduling time, thereby allowing for higher rates on the transmission link and efficient implementation of more complex scheduling algorithms.
The scheduled time slots are serviced in response to a servicing instruction specifying an address in the connection ID table. The connection ID at that location is retrieved, as is the primary scoreboard bit corresponding to that location. The primary scoreboard bit is copied to an assigned cell flag register (ACFR) in the processor, and the scoreboard bit is then cleared to free the time slot for subsequent scheduling requests. The processor then directs the construction or retrieval of a cell for the virtual connection identified by the connection ID retrieved in response to the servicing instruction, and queues the cell for transmission over the ATM link in the scheduled time slot.
Another aspect of the invention involves a method for bounding the primary scoreboard search time to an acceptable range. A secondary scoreboard is generated in the form of a group of stored bits, with each secondary scoreboard bit indicating whether a corresponding block of primary scoreboard bits includes a bit indicative of an available cell time slot. When searching the primary scoreboard in response to a scheduling instruction, an ATM cell processor first directs the retrieval and searching of a block of primary scoreboard bits which includes a target slot specified in the scheduling instruction. If there is no available slot in the retrieved block, the ATM cell processor uses the secondary scoreboard to determine the location of a primary scoreboard block which does include an available slot. The ATM cell processor may access the secondary scoreboard in parallel with its access to the current block of primary scoreboard bits, such that if the current block does not include an available bit, the ATM cell processor already has the secondary scoreboard information identifying a primary scoreboard block which does include an available bit. This parallel access feature accelerates the search process. When an available slot is indicated in a retrieved primary scoreboard block, the remainder of the block is searched to determine if there are any other available slots remaining in that block. If there are no available slots remaining, the secondary scoreboard bit corresponding to the primary scoreboard block is set to indicate that all slots in the block are unavailable. In this manner, the processor does not waste time searching through portions of the primary scoreboard which do not include bits indicating available time slots. The search time can be bounded to a desired number of memory read cycles by appropriate selection of the number of primary scoreboard bits represented by each secondary scoreboard bit. The secondary scoreboard may be maintained in a set of memory locations internal to the ATM cell processor, without unduly increasing the cell processor die size.
Another aspect of the invention involves a technique for handling tunneling operations. One or more virtual path connections each reserve one or more cell time slots in a primary scoreboard for tunneling of virtual channel connections. This primary scoreboard is referred to as a master scoreboard. The master scoreboard bits corresponding to the slots reserved for virtual path connections are set using a suitable scheduling instruction. A separate primary scoreboard, referred to as a tunnel control scoreboard, is generated for each of the virtual path connections which reserve locations on the master scoreboard. The bits of each tunnel control board are configured such that bits corresponding to cell time slots not reserved on the master scoreboard are set to indicate unavailability, while bits corresponding to cell time slots reserved on the primary scoreboard for the given virtual path connection are cleared to indicate availability. The tunnel control boards are used for scheduling virtual channel connections which will use the corresponding virtual path tunnel, such that the connections are directed to the appropriate reserved bit locations.
The scheduled cell time slots are serviced by issuing a servicing instruction. The ATM cell processor may check a block or other portion of the master scoreboard resident in local control memory for an indication of whether a time slot about to be serviced for a given virtual connection is a time slot reserved for a virtual path connection utilizing the tunneling feature. If the ATM cell processor determines that the time slot was reserved for a virtual path connection, the processor determines which virtual channel connection to service by checking the corresponding time slot of the corresponding tunnel control scoreboard. After servicing the connection, the processor reschedules the present cell time in the master scoreboard to re-reserve it for the virtual path connection such that the pre-reserved bandwidth remains available on the transmission link. If the virtual channel connection requires further servicing, the processor reschedules it on the corresponding tunnel control scoreboard. The use of both a master primary scoreboard and separate tunnel control scoreboards for virtual path connections allows a user to, for example, reserve a constant bit rate (CBR) cell stream, represented by a number of master scoreboard bits, on the transmission link for a given virtual path connection, while at the same time using the tunnel control scoreboard to schedule available bit rate (ABR) connections for individual virtual channels on the given virtual path connection.
Another aspect of the invention involves a load multiple instruction which provides a burst transfer of a data block from Fast Access to Software Tables (FAST) control memory, and allows the result of a subsequent operation on a loaded value to be automatically written back to the control memory location from which it was previously read. The instruction may be implemented as a Load Multiple from FAST Memory (LMFM) instruction which specifies the address in the FAST control memory of a data block to be retrieved, a destination register in a CPU register file into which the first retrieved halfword of the data block will be loaded, and a total number of halfwords to be retrieved. The LMFM instruction may also include a link field option which directs the storage of information linking the processor registers which receive the retrieved halfwords to the control memory locations from which the halfwords were read. An automatic memory update feature may then be provided in, for example, an arithmetic logic unit (ALU) instruction which operates on one or more of the processor registers receiving the halfwords retrieved by the LMFM instruction. This feature may be provided by including in the ALU instruction an update memory (UM) field which indicates that the result of the corresponding ALU operation is to be written back to the control memory location or locations which supplied one or more of the operands.
Another aspect of the invention is a modulo arithmetic feature which permits branching on the modulo portion of the result of an arithmetic operation. In an exemplary embodiment, an ALU instruction is modified to include a modulo field which specifies the number of right to left bits after which the result of the corresponding ALU operation will be truncated. Conditional branch instructions such as branch on zero result, branch on non-zero result, branch on negative result, branch on carry and branch on overflow may be configured to operate only on the modulo portion of the ALU instruction result. In other embodiments, a conditional branch could be based in whole or in part on, for example, a carry out of the most significant bit (MSB) position of the modulo portion.
Another aspect of the invention is a cell buffer RAM (CBR) memory space gathering protocol which allows unused portions of a number of cell buffers to be addressed as a contiguous virtual memory space. The space gathering protocol may utilize a CPU or direct memory access (DMA) controller in an ATM cell processor to set a gather bit appended to a virtual CBR address. An address generator in the CBR detects the gather bit and translates those virtual addresses which include a set gather bit to physical addresses into the CBR memory space. The translation is performed by, for example, setting certain bits of the physical address to predetermined states to reach the unused 8 bytes at the bottom of any given 64-byte cell buffer, and shifting certain bits of the virtual address to other positions in the physical address to move from cell buffer to cell buffer in the contiguous virtual space. Multiple gather spaces may be supported in alternative embodiments by using a different number of gather bits. The position of the gather bit or bits in a given set of virtual addresses may vary depending on the CBR memory size.
Another aspect of the invention involves xe2x80x9cbubblexe2x80x9d count techniques which efficiently accommodate multiple layers of scheduling requests and/or external cell sources. In the case of multiple layers of scheduling requests, first and second primary scoreboards are provided for scheduling/servicing of, for example, higher and lower priority traffic, higher and lower cell rate traffic, or externally and internally generated traffic, respectively. A bubble count is maintained for the second scoreboard, and the count is incremented each time the first scoreboard is serviced and decremented each time an idle slot is encountered on the second scoreboard but not queued for transmission. Scheduling requests for the second scoreboard are then made at a target time plus the bubble count. In the case of multiplexing external and internal cell sources, the bubble count may represent the number of cells that have been sent on a given transmission link but not scheduled in the primary scoreboard, and may be incremented each time the primary scoreboard is serviced, and decremented each time an idle slot on the primary scoreboard is encountered but not queued for transmission. Cell servicing in bubble count applications may be facilitated by the use of a pop range (POPR) servicing instruction which specifies a target address on the primary scoreboard and determines if a set bit is found in a range from the target address to the sum of the target address and the bubble count.
Other aspects of the invention include the ability to provide full rate independence among different virtual connections, an inherently fair bandwidth allocation which requires only a single scheduled request to exist on the primary scoreboard at any given time for a given virtual connection to be considered active, the ability to support multiple layers of scheduling requests using multiple scoreboards based on traffic priority or cell rate, and the ability to support multiplexing of cells from an external source with cells constructed or retrieved internally by a cell processor.
An exemplary cell processor in accordance with the present invention overcomes the above-noted problems associated with two-dimensional cell scheduling by in effect removing the second dimension and pushing service requests out in time if a targeted slot is occupied. As a result, each time slot will generally have only a single request pending and subsequent scheduling operations will have a significantly more accurate representation of time. Although a one-dimensional scheduling approach in accordance with the present invention generally utilizes a search of a primary scoreboard representing the cell schedule, the invention provides techniques for performing this scoreboard search in an efficient manner such that overall system throughput performance is improved. For example, an exemplary cell scheduling system in accordance with the invention can find an available cell location in a given range of possible locations within an acceptably bounded time period, by utilizing the secondary scoreboard previously described.
Another advantage of the present invention is that various specialized circuits may be used to handle ATM-specific tasks in conjunction with a CPU in the cell processor. These specialized circuits can offload many time-critical functions from the cell processor CPU to thereby deliver greatly enhanced levels of performance and functionality. An example of such a specialized circuit is the hardware-based traffic shaping mechanism referred to herein as the cell scheduling system (CSS). Although the CSS generally relies on the cell processor CPU for direction regarding required traffic patterns, it can be configured to manage all traffic shaping functions of the ATM cell processing operation. This provides users with the benefits of algorithmic traffic shaping without significant decreases in overall processor throughput performance.
The above-noted features and advantages of the present invention result in a cell processor which in a given embodiment can, for example, (1) operate at speeds of up to 600 Mb/s or more; (2) operate in accordance with the ATM Forum Traffic Management specification for available bit rate (ABR) service; (3) operate as a self-contained device managing concurrent constant bit rate (CBR), variable bit rate (VBR) and ABR connections to thereby free host processing resources for other tasks; (4) support rate-based and quantum flow control based ABR service with algorithmic implementation of traffic shaping; (5) perform in ATM layer processing applications; (6) perform virtual path tunneling whereby a series of VBR, ABR or unspecified bit rate connections can be tunneled across CBR virtual path connections; and/or (7) manage, schedule and traffic shape multiple transmission links simultaneously using multiple scoreboards. These and numerous other features and advantages of the invention provide system designers with a common, reprogrammable cell processor architecture for their ATM products. The present invention thus provides lower ATM product development costs, shorter development cycles and a substantial reduction in the cost of support equipment.